<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>数学模板 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/66.360c2d2b.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>数学模板</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#目录" class="sidebar-link">目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_01-素数筛法" class="sidebar-link">01.素数筛法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_1-1-素数的定义" class="sidebar-link">1.1.素数的定义</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#✅素数相关算法" class="sidebar-link">✅素数相关算法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#判别素数的朴素法（暴力法）" class="sidebar-link">判别素数的朴素法（暴力法）</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#埃塞托尼亚筛" class="sidebar-link">埃塞托尼亚筛</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#欧拉筛" class="sidebar-link">欧拉筛</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_02-快速幂" class="sidebar-link">02.快速幂</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_03-求最大公约数『模板』" class="sidebar-link">03.求最大公约数『模板』</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_04-最小公倍数『模板』" class="sidebar-link">04.最小公倍数『模板』</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_05-约瑟夫环" class="sidebar-link">05.约瑟夫环</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_06-斯特林数（stirling）" class="sidebar-link">06.斯特林数（Stirling）</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_1-题目：" class="sidebar-link">1.题目：</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#ac代码1" class="sidebar-link">AC代码1</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#ac代码2" class="sidebar-link">AC代码2</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#精度问题" class="sidebar-link">精度问题</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_2-斯特林公式" class="sidebar-link">2.斯特林公式</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#找规律题解" class="sidebar-link">找规律题解</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#_1-剑指-offer-44-数字序列中某一位的数字" class="sidebar-link">1.剑指 Offer 44. 数字序列中某一位的数字</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#oj数学题" class="sidebar-link">OJ数学题</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#考点：同余定理" class="sidebar-link">考点：同余定理</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part03.%E6%95%B0%E5%AD%A6%E6%A8%A1%E6%9D%BF.html#格雷码的由来" class="sidebar-link">格雷码的由来</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="数学模板"><a href="#数学模板" class="header-anchor">#</a> 数学模板</h1> <ul><li><a href="https://blog.nowcoder.net/zhuanlan/40nlWj" target="_blank" rel="noopener noreferrer">牛客博客《数学》<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h2 id="目录"><a href="#目录" class="header-anchor">#</a> 目录</h2> <p>[TOC]</p> <h2 id="_01-素数筛法"><a href="#_01-素数筛法" class="header-anchor">#</a> 01.素数筛法</h2> <ul><li>素数暴力到欧拉筛法</li></ul> <p>本文讲解了<strong>素数</strong> 的定义
并且从素数的暴力算法一路优化到了欧拉筛法</p> <h3 id="_1-1-素数的定义"><a href="#_1-1-素数的定义" class="header-anchor">#</a> 1.1.素数的定义</h3> <p>维基百科定义：<br> <strong>质数</strong>（Prime number），又称<strong>素数</strong><br> <strong>指在大于1的自然数中</strong>，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为<strong>合数</strong>（也称为<strong>合成数</strong>）。<br> <strong>Tips：</strong><br>
1.有的教材上：（指在大于1的自然数中）这一点没有强调，导致容易误解！！！<br>
也是经常弄晕一些人对素数的理解的原因。<br>
2.所以：<font size="3" style="background:yellow;">1既不是素数也不是合数！！！</font></p> <h3 id="✅素数相关算法"><a href="#✅素数相关算法" class="header-anchor">#</a> ✅素数相关算法</h3> <h3 id="判别素数的朴素法（暴力法）"><a href="#判别素数的朴素法（暴力法）" class="header-anchor">#</a> 判别素数的朴素法（暴力法）</h3> <span id="jump021"></span> <h5 id="_1）算法原理："><a href="#_1）算法原理：" class="header-anchor">#</a> 1）算法原理：</h5> <p>不管三七二十一
根据素数定义就是一顿暴力。</p> <h5 id="_2）实现-轻微优化"><a href="#_2）实现-轻微优化" class="header-anchor">#</a> 2）实现(轻微优化)</h5> <h6 id="代码段："><a href="#代码段：" class="header-anchor">#</a> 代码段：</h6> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">isPrime</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//0表示不是素数，1表示是素数 </span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">&lt;=</span><span class="token number">1</span><span class="token punctuation">)</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> 
	<span class="token comment">//表示根号n向下取整 </span>
	<span class="token keyword">int</span> sqrt_num<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token function">sqrt</span><span class="token punctuation">(</span><span class="token number">1.0</span><span class="token operator">*</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>sqrt_num<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">%</span>i<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	 <span class="token punctuation">}</span> 
	
	<span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//是素数 </span>
<span class="token punctuation">}</span>


</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><h3 id="埃塞托尼亚筛"><a href="#埃塞托尼亚筛" class="header-anchor">#</a> 埃塞托尼亚筛</h3> <span id="jump022"></span> <h5 id="_1）算法原理：-2"><a href="#_1）算法原理：-2" class="header-anchor">#</a> 1）算法原理：</h5> <p>1&gt;假设从2-N全是素数
2&gt;从2开始枚举，对于每个素数，我们筛去它的所有倍数，最后我们剩下来的就都是素数
<strong>关键点</strong>：
从2开始枚举到某个数字A，如果a没有被前面步骤的数筛去，那么a一定是素数。
原因：
<strong>如果A（A&gt;2）是合数</strong>，则<strong>A=素数×另一个数</strong><br> <strong>PS：这个素数必定小于A，所以会被我们前面筛出来的素数筛掉</strong></p> <h5 id="_2）实现"><a href="#_2）实现" class="header-anchor">#</a> 2）实现</h5> <p>用一个标记数组实现
枚举的过程中，筛的过程就是依次改变这个标记数组的过程</p> <h5 id="实现1：按照思路直接筛，筛的过程如下图红色箭头所示"><a href="#实现1：按照思路直接筛，筛的过程如下图红色箭头所示" class="header-anchor">#</a> 实现1：按照思路直接筛，筛的过程如下图红色箭头所示</h5> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020_5.26_1.png" alt="2020_5.26_1"></p> <h6 id="代码段：-2"><a href="#代码段：-2" class="header-anchor">#</a> 代码段：</h6> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//Eratosthenes_one.cpp </span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">100000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>

<span class="token comment">//除了0,1之外(因为0和1既不是合数，也不是素数)</span>
<span class="token comment">//TagArray数组中，0表示i是素数，1表示是合数</span>
<span class="token keyword">int</span> TagArray<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">//Prime数组中存放素数(从0号位开始放)</span>
<span class="token comment">//Num表示Prime数组中素数的个数 </span>
<span class="token keyword">int</span> Prime<span class="token punctuation">[</span><span class="token number">10000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> Num<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxn<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>TagArray<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token comment">//如果标记数组说i这个数是素数 </span>
		<span class="token punctuation">{</span>
			Prime<span class="token punctuation">[</span>Num<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span><span class="token comment">//存素数i，并且Num+1</span>
			
			<span class="token comment">//注意这种写法，本来应该用i*j&lt;=(maxn-1)判断就好了</span>
			<span class="token comment">//但是要避免i*j的结果溢出int,所以改为j&lt;=((maxn-1)/i)</span>
			<span class="token comment">//maxn-1是因为标记数组范围本来就只有0-100004 </span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token punctuation">(</span><span class="token punctuation">(</span>maxn<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">/</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				TagArray<span class="token punctuation">[</span>j<span class="token operator">*</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//筛去素数i的倍数 </span>
			<span class="token punctuation">}</span>
			
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	
<span class="token punctuation">}</span> 


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//求1-100000+4中哪些是素数</span>
	<span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;正整数100004内素数的个数:%d\n&quot;</span><span class="token punctuation">,</span>Num<span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>Num<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>Prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br></div></div><h5 id="实现2："><a href="#实现2：" class="header-anchor">#</a> 实现2：</h5> <p>在实现1的基础上，我们发现，如图中蓝色部分的，被重复筛了。我们容易观察出，如果要减少筛的次数，我们可以从质数的平方往后筛（优化）</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020_5.26_2.png" alt="2020_5.26_2"></p> <h6 id="代码段：-3"><a href="#代码段：-3" class="header-anchor">#</a> 代码段：</h6> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//Eratosthenes_two.cpp</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">100000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>

<span class="token comment">//除了0,1之外(因为0和1既不是合数，也不是素数)</span>
<span class="token comment">//TagArray数组中，0表示i是素数，1表示是合数</span>
<span class="token keyword">int</span> TagArray<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">//Prime数组中存放素数(从0号位开始放)</span>
<span class="token comment">//Num表示Prime数组中素数的个数 </span>
<span class="token keyword">int</span> Prime<span class="token punctuation">[</span><span class="token number">10000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> Num<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxn<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>TagArray<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token comment">//如果标记数组说i这个数是素数 </span>
		<span class="token punctuation">{</span>
			Prime<span class="token punctuation">[</span>Num<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span><span class="token comment">//存素数i，并且Num+1</span>
			
			<span class="token comment">//注意这种写法，本来应该用i*j&lt;=(maxn-1)判断就好了</span>
			<span class="token comment">//但是要避免i*j的结果溢出int,所以改为j&lt;=((maxn-1)/i)</span>
			<span class="token comment">//maxn-1是因为标记数组范围本来就只有0-100004 </span>
			<span class="token comment">//(修改处)将j=2改为了j=i，这样就能少筛掉表格中那些蓝色部分了 </span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token punctuation">;</span> j<span class="token operator">&lt;=</span><span class="token punctuation">(</span><span class="token punctuation">(</span>maxn<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">/</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>j<span class="token punctuation">)</span> 
			<span class="token punctuation">{</span>
				TagArray<span class="token punctuation">[</span>j<span class="token operator">*</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//筛去素数i的倍数 </span>
			<span class="token punctuation">}</span>
			
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	
<span class="token punctuation">}</span> 


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//求1-100000+4中哪些是素数</span>
	<span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;正整数100004内素数的个数:%d\n&quot;</span><span class="token punctuation">,</span>Num<span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>Num<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>Prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br></div></div><h3 id="欧拉筛"><a href="#欧拉筛" class="header-anchor">#</a> 欧拉筛</h3> <span id="jump023"></span> <p><strong>由来</strong>：
由于埃塞托尼亚筛筛的时候重复筛（比如下面的）了，使得算法效率还不够好，所以，我们改进一下，我们继续观察先前的图，发现埃塞托尼亚筛是<strong>竖着筛</strong>，我们似乎也难以优化这种筛法了，我们转换一下思路——<strong>横着筛</strong></p> <h5 id="_1）算法原理：-3"><a href="#_1）算法原理：-3" class="header-anchor">#</a> 1）算法原理：</h5> <p>思路：在埃氏筛的一种优化<br>
任何合数都能写成一个素数乘一个数（显然这个素数不一定是唯一的）<br>
//举个例子：12=2<em>6=3</em>4（2和3都是素数）<br>
所以，任何合数都有一个<strong>最小的质因数</strong></p> <table><tr><td bgcolor="#FFFF" FF>用这个&quot;最小质因数&quot;来判断什么时候不用继续筛下去
</td></tr></table> <p>那么如何实现呢？<br>
欧拉研究发现，我要是<strong>横着筛</strong>就会比前面那种只优化掉蓝色部分的埃氏筛还快</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020_5.26_3.png" alt="2020_5.26_3"></p> <p><strong>注意</strong>：这里是横着筛，此外图中箭头从<strong>橙色出发（包括该点）<strong>往右的所有我都不筛<br>
具体实现方法是用的一个</strong>break</strong>实现的。</p> <h5 id="_2）实现-2"><a href="#_2）实现-2" class="header-anchor">#</a> 2）实现</h5> <h6 id="代码段：-4"><a href="#代码段：-4" class="header-anchor">#</a> 代码段：</h6> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//Euler.cpp</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">100000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>

<span class="token comment">//除了0,1之外(因为0和1既不是合数，也不是素数)</span>
<span class="token comment">//TagArray数组中，0表示i是素数，1表示是合数</span>
<span class="token keyword">int</span> TagArray<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">//Prime数组中存放素数(从0号位开始放)</span>
<span class="token comment">//Num表示Prime数组中素数的个数 </span>
<span class="token keyword">int</span> Prime<span class="token punctuation">[</span><span class="token number">10000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> Num<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxn<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>TagArray<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token comment">//如果标记数组说i这个数是素数 </span>
		<span class="token punctuation">{</span>
			Prime<span class="token punctuation">[</span>Num<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span><span class="token comment">//存素数，并且Num+1	</span>
		<span class="token punctuation">}</span>
		
		
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">(</span>j<span class="token operator">&lt;</span>Num<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span><span class="token punctuation">(</span>i<span class="token operator">&lt;=</span><span class="token punctuation">(</span><span class="token punctuation">(</span>maxn<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">/</span>Prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token operator">++</span>j<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token comment">//一进来,不管三七二十一，先筛掉一个先</span>
			TagArray<span class="token punctuation">[</span>i<span class="token operator">*</span>Prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">%</span>Prime<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token comment">//判别i是Prime数组中某个的倍数，则跳出，</span>
				<span class="token comment">//这行后面的也不用筛 	</span>
				<span class="token keyword">break</span><span class="token punctuation">;</span>
			 <span class="token punctuation">}</span> 	
			 
		 <span class="token punctuation">}</span>
		
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span> 


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//求1-100000+5-1中哪些是素数</span>
	<span class="token function">FindPrime</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;正整数100004内素数的个数:%d\n&quot;</span><span class="token punctuation">,</span>Num<span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>Num<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>Prime<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	 
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br></div></div><h2 id="_02-快速幂"><a href="#_02-快速幂" class="header-anchor">#</a> 02.快速幂</h2> <ul><li>求a<sup>b</sup>%m</li> <li>下面的式子还使用了『同余定理』</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">LLow</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> a<span class="token punctuation">,</span> <span class="token keyword">long</span> <span class="token keyword">long</span> b<span class="token punctuation">,</span> <span class="token keyword">long</span> <span class="token keyword">long</span> m<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    
    <span class="token keyword">while</span><span class="token punctuation">(</span> b<span class="token operator">&gt;</span><span class="token number">0</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//如果b是偶数</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> b<span class="token operator">&amp;</span><span class="token number">1</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            ans<span class="token operator">=</span>ans<span class="token operator">*</span>a<span class="token operator">%</span>m<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        a<span class="token operator">=</span>a<span class="token operator">*</span>a<span class="token operator">%</span>m<span class="token punctuation">;</span>
        b<span class="token operator">&gt;&gt;=</span><span class="token number">1</span><span class="token punctuation">;</span>
        
    <span class="token punctuation">}</span>
    
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br></div></div><h2 id="_03-求最大公约数『模板』"><a href="#_03-求最大公约数『模板』" class="header-anchor">#</a> 03.求最大公约数『模板』</h2> <ul><li>题目传送门：<a href="https://www.nowcoder.com/practice/731b967dcda845669fee8c41f0b16e8b" target="_blank" rel="noopener noreferrer">一行代码求两个数的最大公约数<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>辗转相除法『迭代写法』</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">gcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span><span class="token keyword">int</span> b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> a<span class="token operator">&lt;</span>b <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">swap</span><span class="token punctuation">(</span> a<span class="token punctuation">,</span>b <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> a<span class="token operator">%</span>b <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> temp<span class="token operator">=</span>a<span class="token operator">%</span>b<span class="token punctuation">;</span>
		a<span class="token operator">=</span>b<span class="token punctuation">;</span>
		b<span class="token operator">=</span>temp<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> b<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">)</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span><span class="token function">gcd</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span>m<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br></div></div><h2 id="_04-最小公倍数『模板』"><a href="#_04-最小公倍数『模板』" class="header-anchor">#</a> 04.最小公倍数『模板』</h2> <ul><li>和『最大公约数』关系密切</li> <li>得到最大公约数后，很简单</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">lcm</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> gcdNum<span class="token operator">=</span><span class="token function">gcd</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> a<span class="token operator">/</span>gcdNum<span class="token operator">*</span>b<span class="token punctuation">;</span>	<span class="token comment">//注意，这种防止溢出的写法</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h2 id="_05-约瑟夫环"><a href="#_05-约瑟夫环" class="header-anchor">#</a> 05.约瑟夫环</h2> <ul><li><a href="https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/" target="_blank" rel="noopener noreferrer">剑指 Offer 62. 圆圈中最后剩下的数字<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>参考<a href="https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/si-bu-he-xin-gong-shi-qing-song-nong-don-3vln/" target="_blank" rel="noopener noreferrer">原理<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h2 id="_06-斯特林数（stirling）"><a href="#_06-斯特林数（stirling）" class="header-anchor">#</a> 06.斯特林数（Stirling）</h2> <h3 id="_1-题目："><a href="#_1-题目：" class="header-anchor">#</a> 1.题目：</h3> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>Number lengths
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 1411, Accepted users: 1317
Problem 10146 : No special judgement
Problem description
N! (N factorial) can be quite irritating and difficult to compute for large values of N. So instead of calculating N!, I want to know how many digits are in it. (Remember that N! = N * (N - 1) * (N - 2) * ... * 2 * 1)

Input
Each line of the input will have a single integer N on it 0 &lt; N &lt; 1000000 (1 million). Input is terminated by end of file.

Output
For each value of N, print out how many digits are in N!.

Sample Input
1
3
32000
1000000
Sample Output
1 
1
130271
5565709
Problem Source
UD Contest
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br></div></div><h3 id="ac代码1"><a href="#ac代码1" class="header-anchor">#</a> AC代码1</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//考点：数学</span>
<span class="token comment">//打表技巧 </span>
<span class="token comment">//注意点，关于如何弄出精度，</span>
<span class="token comment">//原先想到的是斯特林公式，但是后面发现，都不需要这个 </span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath&gt;</span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span>  maxn<span class="token operator">=</span><span class="token number">1000000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>
<span class="token keyword">double</span> a<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxn<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//主要的保证精度的地方 </span>
        a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>a<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token function">log10</span><span class="token punctuation">(</span><span class="token number">1.0</span><span class="token operator">*</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    
    <span class="token keyword">int</span> n<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>a<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
        
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br></div></div><p>总结：
刚开始以为可以递归找规律，结果半点也没找出来0.0</p> <ul><li>注意：<strong>log10（x）就是求x的十进制位数，log（x）就是求x的二进制位数</strong></li></ul> <p>其他人的想法：</p> <ul><li>刚刚听大神说这题维护前11位也可以过，可是我比赛时想的只是维护首位，然后发现到十几的时候就错了，所以就放弃了</li></ul> <h3 id="ac代码2"><a href="#ac代码2" class="header-anchor">#</a> AC代码2</h3> <ul><li><p>给出一个数N，求出N！的位数。
暴力法肯定是不行的，阶乘是个增长速度 很快的函数，10！已经有7位了。</p></li> <li><p>更直接的方法是log10(N!)  --以10为底N!的对数。 因为求位数就是要每次除以10 的，取对数的意义就是10的几次方才能到N!，也就是求了N!有几位。</p></li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>那么问题就转化成求log10(N!)了
一种方法是换底公式然后求和log10(N!) = log2(1*2*3*..*N)/log2(10)分子拆开求和
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h3 id="精度问题"><a href="#精度问题" class="header-anchor">#</a> 精度问题</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> n<span class="token punctuation">,</span>m<span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>n<span class="token operator">--</span><span class="token punctuation">)</span><span class="token comment">//数据组数</span>
    <span class="token punctuation">{</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">double</span> a<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>b<span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
            a<span class="token operator">+=</span> <span class="token function">log</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
        a<span class="token operator">/=</span> <span class="token function">log</span><span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>a<span class="token punctuation">;</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>ans<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//实践证明不+1总是少一位，大概是double舍入的问题？</span>
    <span class="token punctuation">}</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br></div></div><p>此外，还有斯特林公式，也可以用来估计一些数字，OJ崩了，待补。</p> <h3 id="_2-斯特林公式"><a href="#_2-斯特林公式" class="header-anchor">#</a> 2.斯特林公式</h3> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/Stirling.png" alt="Stirling"></p> <h2 id="找规律题解"><a href="#找规律题解" class="header-anchor">#</a> 找规律题解</h2> <h3 id="_1-剑指-offer-44-数字序列中某一位的数字"><a href="#_1-剑指-offer-44-数字序列中某一位的数字" class="header-anchor">#</a> 1.<a href="https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/" target="_blank" rel="noopener noreferrer">剑指 Offer 44. 数字序列中某一位的数字<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <ul><li><a href="https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/" target="_blank" rel="noopener noreferrer">剑指 Offer 44. 数字序列中某一位的数字<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li><a href="https://leetcode-cn.com/problems/nth-digit/" target="_blank" rel="noopener noreferrer">400. 第 N 位数字<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="oj数学题"><a href="#oj数学题" class="header-anchor">#</a> OJ数学题</h3> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>Reduced ID Numbers 
Time Limit: 2000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 624, Accepted users: 574
Problem 10275 : No special judgement
Problem description
T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 106-1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.

Input
On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs within a group are distinct, though not necessarily sorted.

Output
For each test case, output one line containing the smallest modulus m, such that all SINs reduced modulo m are distinct.

Sample Input
2
1
124866
3
124866
111111
987651
Sample Output
1
8
Problem Source
NWERC 2005
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br></div></div><h3 id="考点：同余定理"><a href="#考点：同余定理" class="header-anchor">#</a> 考点：同余定理</h3> <p>这道题是对同余定理的考查，思路很简单，暴力地枚举j，直到j满足集合中任意两个数对j取余都不相等，此时停止循环；</p> <p>对于代码中的memset，比用for循环初始化为0快，只是在数组大的时候。在数组大小比较小时则for初始化比较省时（我在这超时了4、5次了）</p> <p>一共是n个学生，所以去完模之后至少要有n个不同的值，所有程序里面的j要从n开始的。当然从1开始也不会错，只是一个小小的优化吧。</p> <p>代码如下：</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;stdio.h&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;string.h&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;math.h&gt;</span></span>

<span class="token keyword">int</span> a<span class="token punctuation">[</span><span class="token number">10000001</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">,</span>n<span class="token punctuation">;</span>
	<span class="token keyword">int</span> cas<span class="token punctuation">,</span>ans<span class="token punctuation">,</span>t<span class="token punctuation">;</span>
	<span class="token keyword">int</span> s<span class="token punctuation">[</span><span class="token number">303</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> f<span class="token punctuation">;</span>
	<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>cas<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>cas<span class="token operator">--</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
			<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span>n<span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">1000000</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			f<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>j<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>		<span class="token comment">//这里用memset的话会超时的！</span>
				a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
			<span class="token punctuation">{</span>
				<span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">%</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>
				<span class="token punctuation">{</span>
					f<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
					<span class="token keyword">break</span><span class="token punctuation">;</span>
				<span class="token punctuation">}</span>
				a<span class="token punctuation">[</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">%</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>	
			<span class="token punctuation">}</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>f<span class="token punctuation">)</span>
				<span class="token keyword">break</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br></div></div><ul><li>湖大OJ上还能用gets『2020年记载的』</li></ul> <h2 id="格雷码的由来"><a href="#格雷码的由来" class="header-anchor">#</a> 格雷码的由来</h2> <ul><li>LeetCode<a href="https://leetcode-cn.com/problems/gray-code/" target="_blank" rel="noopener noreferrer">89. 格雷编码<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li><a href="https://leetcode-cn.com/problems/gray-code/solution/c5xing-dai-ma-xiang-xi-jie-xi-dui-xin-sh-xrkw/" target="_blank" rel="noopener noreferrer">由来<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>「数学」</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">grayCode</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> res<span class="token punctuation">;</span>
        <span class="token keyword">int</span> count<span class="token operator">=</span><span class="token number">1</span><span class="token operator">&lt;&lt;</span>n<span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> loop<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> loop<span class="token operator">&lt;</span>count<span class="token punctuation">;</span> <span class="token operator">++</span>loop<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> loop<span class="token operator">^</span><span class="token punctuation">(</span> loop<span class="token operator">&gt;&gt;</span><span class="token number">1</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br></div></div></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/66.360c2d2b.js" defer></script>
  </body>
</html>
